package com.stefan.sort;

/*
* 希尔排序是对插入排序的增强，增强的是break的次数，
* 目的是使大多数的数组是有序的，然后break的次数会多。
* 多了层循环，不是每次+1
* */
public class ShellSort {
    public static void main(String[] args) {
        int[] data = {7,9,3,2,4,6,0,5,1,8};
        System.out.print("排序前：");
        for (int m = 0; m < data.length; m++) {
            System.out.print(data[m]);
        }
        System.out.println("");
        int len = data.length;
        for (int xier = len/2; xier >=1 ; xier/=2) {
            for (int i = xier; i < len; i++) { //从xier开始，是第一个元素data[0]不用排序，归入排好序的部分。0-i是排好序的，i后面是要比较的值
                int current = data[i]; //未排序的开始，也就是要进行比较的那个元素
                int j = i-xier;
                for (;j>=0; j-=xier) {
                    if (data[j] > current) {
                        data[j+xier] = data[j];
//                    data[j+1] = pre;
                    } else {
                        break; // 当前要比较的元素比排好序的元素中的一个大，那就停止比较
                    }
                }
                data[j+xier] = current;
                System.out.print("第"+i+"轮后：");
                for (int m = 0; m < len; m++) {
                    System.out.print(data[m]);
                }
                System.out.println("");
            }
        }
    }

}
